<!doctype html>
<html lang="zh-CN">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>归并排序与逆序对问题</title>
    <link rel="stylesheet" href="https://cdn.staticfile.org/font-awesome/6.4.0/css/all.min.css">
    <link rel="stylesheet" href="https://cdn.staticfile.org/tailwindcss/2.2.19/tailwind.min.css">
    <link href="https://fonts.googleapis.com/css2?family=Noto+Serif+SC:wght@400;500;600;700&family=Noto+Sans+SC:wght@300;400;500;700&display=swap" rel="stylesheet">
    <script src="https://cdn.jsdelivr.net/npm/mermaid@latest/dist/mermaid.min.js"></script>
    <style>
        body {
            font-family: 'Noto Sans SC', Tahoma, Arial, Roboto, "Droid Sans", "Helvetica Neue", "Droid Sans Fallback", "Heiti SC", "Hiragino Sans GB", Simsun, sans-serif;
            background: linear-gradient(135deg, #f5f7fa 0%, #c3cfe2 100%);
            min-height: 100vh;
        }
        .hero-gradient {
            background: linear-gradient(135deg, #667eea 0%, #764ba2 100%);
        }
        .card-hover {
            transition: all 0.3s ease;
        }
        .card-hover:hover {
            transform: translateY(-5px);
            box-shadow: 0 20px 40px rgba(0,0,0,0.1);
        }
        .code-block {
            background: #282c34;
            color: #abb2bf;
            border-radius: 8px;
            overflow-x: auto;
        }
        .code-block pre {
            margin: 0;
            padding: 1.5rem;
            font-family: 'Consolas', 'Monaco', monospace;
            font-size: 14px;
            line-height: 1.6;
        }
        .keyword { color: #c678dd; }
        .function { color: #61afef; }
        .string { color: #98c379; }
        .number { color: #d19a66; }
        .comment { color: #5c6370; font-style: italic; }
        .operator { color: #56b6c2; }
        .first-letter {
            float: left;
            font-size: 4rem;
            line-height: 3rem;
            padding-right: 0.5rem;
            font-weight: 700;
            color: #667eea;
            font-family: 'Noto Serif SC', serif;
        }
        .mermaid {
            display: flex;
            justify-content: center;
            margin: 2rem 0;
        }
        @keyframes fadeIn {
            from { opacity: 0; transform: translateY(20px); }
            to { opacity: 1; transform: translateY(0); }
        }
        .fade-in {
            animation: fadeIn 0.8s ease-out;
        }
    </style>
</head>
<body>
    <!-- Hero Section -->
    <section class="hero-gradient text-white py-20 px-6">
        <div class="max-w-6xl mx-auto text-center fade-in">
            <h1 class="text-5xl md:text-6xl font-bold mb-6">
                <i class="fas fa-code-branch mr-4"></i>归并排序与逆序对
            </h1>
            <p class="text-xl md:text-2xl opacity-90 max-w-3xl mx-auto">
                探索分治思想的优雅实现，在 O(n log n) 时间内解决逆序对统计问题
            </p>
        </div>
    </section>

    <!-- Main Content -->
    <main class="max-w-6xl mx-auto px-6 py-12">
        <!-- Problem Description Card -->
        <div class="bg-white rounded-2xl shadow-xl p-8 mb-8 card-hover fade-in">
            <div class="flex items-center mb-6">
                <div class="bg-purple-100 p-3 rounded-full mr-4">
                    <i class="fas fa-puzzle-piece text-purple-600 text-2xl"></i>
                </div>
                <h2 class="text-3xl font-bold text-gray-800">问题描述</h2>
            </div>
            <p class="text-lg text-gray-700 leading-relaxed">
                <span class="first-letter">给</span>定一个数组，统计其中的逆序对数量。逆序对指的是数组中前面的数大于后面的数。例如，在数组 [2, 4, 1, 3, 5] 中，逆序对有 (2,1)、(4,1)、(4,3)，共3对。要求使用归并排序思想高效实现。
            </p>
        </div>

        <!-- Core Concepts Grid -->
        <div class="grid md:grid-cols-2 gap-6 mb-8">
            <div class="bg-white rounded-xl shadow-lg p-6 card-hover fade-in">
                <div class="flex items-center mb-4">
                    <i class="fas fa-brain text-indigo-600 text-2xl mr-3"></i>
                    <h3 class="text-xl font-bold text-gray-800">核心算法</h3>
                </div>
                <div class="space-y-3">
                    <div class="flex items-center">
                        <span class="bg-indigo-100 text-indigo-700 px-3 py-1 rounded-full text-sm font-medium">分治思想</span>
                        <span class="ml-3 text-gray-600">将问题分解为子问题求解</span>
                    </div>
                    <div class="flex items-center">
                        <span class="bg-purple-100 text-purple-700 px-3 py-1 rounded-full text-sm font-medium">归并排序</span>
                        <span class="ml-3 text-gray-600">在合并过程中统计逆序对</span>
                    </div>
                </div>
            </div>

            <div class="bg-white rounded-xl shadow-lg p-6 card-hover fade-in">
                <div class="flex items-center mb-4">
                    <i class="fas fa-clock text-green-600 text-2xl mr-3"></i>
                    <h3 class="text-xl font-bold text-gray-800">复杂度分析</h3>
                </div>
                <div class="space-y-3">
                    <div class="flex items-center">
                        <span class="bg-green-100 text-green-700 px-3 py-1 rounded-full text-sm font-medium">时间复杂度</span>
                        <span class="ml-3 text-gray-600 font-mono">O(n log n)</span>
                    </div>
                    <div class="flex items-center">
                        <span class="bg-blue-100 text-blue-700 px-3 py-1 rounded-full text-sm font-medium">空间复杂度</span>
                        <span class="ml-3 text-gray-600 font-mono">O(n)</span>
                    </div>
                </div>
            </div>
        </div>

        <!-- Algorithm Visualization -->
        <div class="bg-white rounded-2xl shadow-xl p-8 mb-8 fade-in">
            <h2 class="text-2xl font-bold text-gray-800 mb-6 flex items-center">
                <i class="fas fa-sitemap text-indigo-600 mr-3"></i>
                算法流程图
            </h2>
            <div class="mermaid">
                graph TD
                    A[原始数组] --> B[分割成左右两部分]
                    B --> C[递归排序左半部分]
                    B --> D[递归排序右半部分]
                    C --> E[合并左右部分]
                    D --> E
                    E --> F[统计跨越左右的逆序对]
                    F --> G[返回排序后数组和逆序对总数]
                    
                    style A fill:#667eea,stroke:#fff,stroke-width:2px,color:#fff
                    style G fill:#48bb78,stroke:#fff,stroke-width:2px,color:#fff
                    style F fill:#f56565,stroke:#fff,stroke-width:2px,color:#fff
            </div>
        </div>

        <!-- Solution Approach -->
        <div class="bg-gradient-to-r from-indigo-50 to-purple-50 rounded-2xl p-8 mb-8 fade-in">
            <h2 class="text-2xl font-bold text-gray-800 mb-6 flex items-center">
                <i class="fas fa-lightbulb text-yellow-500 mr-3"></i>
                解题思路
            </h2>
            <div class="grid md:grid-cols-3 gap-6">
                <div class="bg-white rounded-lg p-6 shadow-md">
                    <div class="text-4xl font-bold text-indigo-600 mb-3">1</div>
                    <h4 class="font-bold text-gray-800 mb-2">分解问题</h4>
                    <p class="text-gray-600">将数组递归地分成两半，直到每个子数组只有一个元素</p>
                </div>
                <div class="bg-white rounded-lg p-6 shadow-md">
                    <div class="text-4xl font-bold text-purple-600 mb-3">2</div>
                    <h4 class="font-bold text-gray-800 mb-2">合并统计</h4>
                    <p class="text-gray-600">在合并过程中，当左侧元素大于右侧元素时，统计逆序对数量</p>
                </div>
                <div class="bg-white rounded-lg p-6 shadow-md">
                    <div class="text-4xl font-bold text-green-600 mb-3">3</div>
                    <h4 class="font-bold text-gray-800 mb-2">累加结果</h4>
                    <p class="text-gray-600">将左右子数组的逆序对数与跨越逆序对数相加</p>
                </div>
            </div>
        </div>

        <!-- Code Implementation -->
        <div class="bg-white rounded-2xl shadow-xl p-8 mb-8 fade-in">
            <h2 class="text-2xl font-bold text-gray-800 mb-6 flex items-center">
                <i class="fas fa-code text-green-600 mr-3"></i>
                示例代码
            </h2>
            <div class="code-block">
                <pre><code><span class="keyword">def</span> <span class="function">mergeSortInversions</span>(nums):
    <span class="keyword">def</span> <span class="function">merge</span>(left, right):
        result = []
        count = <span class="number">0</span>
        i = j = <span class="number">0</span>
        <span class="keyword">while</span> i <span class="operator">&lt;</span> <span class="function">len</span>(left) <span class="keyword">and</span> j <span class="operator">&lt;</span> <span class="function">len</span>(right):
            <span class="keyword">if</span> left[i] <span class="operator">&lt;=</span> right[j]:
                result.append(left[i])
                i <span class="operator">+=</span> <span class="number">1</span>
            <span class="keyword">else</span>:
                result.append(right[j])
                count <span class="operator">+=</span> <span class="function">len</span>(left) <span class="operator">-</span> i  <span class="comment"># 关键：统计逆序对</span>
                j <span class="operator">+=</span> <span class="number">1</span>
        result.extend(left[i:])
        result.extend(right[j:])
        <span class="keyword">return</span> result, count
    
    <span class="keyword">def</span> <span class="function">sort</span>(nums):
        <span class="keyword">if</span> <span class="function">len</span>(nums) <span class="operator">&lt;=</span> <span class="number">1</span>:
            <span class="keyword">return</span> nums, <span class="number">0</span>
        mid = <span class="function">len</span>(nums) <span class="operator">//</span> <span class="number">2</span>
        left, left_count = sort(nums[:mid])
        right, right_count = sort(nums[mid:])
        merged, merge_count = merge(left, right)
        <span class="keyword">return</span> merged, left_count <span class="operator">+</span> right_count <span class="operator">+</span> merge_count
    
    <span class="keyword">return</span> sort(nums)[<span class="number">1</span>]</code></pre>
            </div>
        </div>

        <!-- Key Insights -->
        <div class="bg-gradient-to-br from-yellow-50 to-orange-50 rounded-2xl p-8 fade-in">
            <h2 class="text-2xl font-bold text-gray-800 mb-6 flex items-center">
                <i class="fas fa-key text-orange-500 mr-3"></i>
                关键洞察
            </h2>
            <div class="grid md:grid-cols-2 gap-6">
                <div class="flex items-start">
                    <div class="bg-orange-100 p-2 rounded-full mr-4 mt-1">
                        <i class="fas fa-check text-orange-600"></i>
                    </div>
                    <div>
                        <h4 class="font-bold text-gray-800 mb-2">为什么能统计逆序对？</h4>
                        <p class="text-gray-600">在合并两个已排序数组时，如果左侧元素大于右侧元素，那么左侧该元素及其后面的所有元素都与右侧当前元素构成逆序对。</p>
                    </div>
                </div>
                <div class="flex items-start">
                    <div class="bg-orange-100 p-2 rounded-full mr-4 mt-1">
                        <i class="fas fa-rocket text-orange-600"></i>
                    </div>
                    <div>
                        <h4 class="font-bold text-gray-800 mb-2">效率优势</h4>
                        <p class="text-gray-600">相比暴力解法的 O(n²) 复杂度，归并排序方法将问题优化到 O(